Trees ===== What are some applications of trees? File directory structure Searching Expression evaluation Non-recursive definition of a tree: Set of nodes Set of directed edges One node is root Every node (except root) connected from exactly one parent Recursive definition of a tree: Either tree is empty Or tree is root and zero or more subtrees Roots of subtrees T1..Tk connected from root How many edges are there in a tree with N nodes? N - 1 Every node except the root has an incoming edge Some terminology: Parent X is the parent of Y if there is directed edge from X to Y Child X is a child of Y if Y is the parent of X Sibling X is a sibling of Y if X and Y have the same parent Path A path from X to Y is a sequence of connected edges starting at X and ending at Y Length of a path The length of a path is the number of edges it contains Ancestor X is an ancestor of Y if there is a path from X to Y Proper ancestor X is a proper ancestor of Y if it is an ancestor of Y and X<>Y Descendant X is a descendant of Y is Y is an ancestor of X Proper descendant X is a proper descendant of Y if it is a descendant of Y and X<>Y Leaf A leaf is a childless node Depth of a node The depth of a node X is the length of the path from the root to X The depth of a node is 1 more than the depth of its parent Depth of the root The depth of the root is defined as 0 Height of a node The height of a node X is the length of the path from X to the deepest leaf The height of a node is 1 more than the height of its maximum-height child Height of a leaf The height of a leaf is defined as 0 Height of a tree The height of a tree is the height of its root Size of a node The size of a node X is the number of descendants of X + 1 (i.e., X is included) Size of a tree The size of a tree is the size of its root Implementation Issues --------------------- What should be stored in each tree node object? A reference to the data stored at the node References to the children of the node How should you store the references to the children? Draw the tree with nodes containing arrays of child references What's the problem with using arrays of child references? How can you store the child references without a fixed size array? First-child/next-sibling Each node has two links One to leftmost child One to the next sibling Draw the tree with nodes containing first-child/next-sibling What does it mean to traverse a tree? What are some applications of tree traversal? print all the values stored in the tree Search the tree for a particular value Find the maximum value in a tree Compute the height of the tree What's a preorder traversal? What's a postorder traversal? (a) Tree.java Binary Trees ------------ What are some applications of binary trees? Expression evaluation Huffman compression Binary search tree Priority queue Give a non-recursive definition of a binary tree. A tree where nodes have at most 2 children Give a recursive definition of a binary tree. Either tree is empty Or tree is composed of a root, a left tree, and a right tree How many different binary trees are there with exactly 2 nodes? Implementation Issues: What should be stored in each binary tree node object? Reference to the data stored at the node Reference to the left child Reference to the right child (b) BinaryTree.java How do you traverse a binary tree: in preorder? in postorder? in inorder? How can you traverse a tree without using recursion? Use a stack Write preorder Iterator for a binary tree What happens to the Iterator if we use a Queue instead of a Stack? We get level-order instead of preorder Write a level-order Iterator for a binary tree (c) TreeIter.java How can you represent an expression as a binary tree? Leaves are operands Other nodes are operators How do you construct an expression tree? Parse the expression How do you use the tree to evaluate the expression? Apply the operator at the root to the result of recursively evaluating the left and right subtrees (d) ExprTree.java